Leetcode 23. merge-k-sorted-lists 题解 - Week6

题目链接

Leetcode 23. merge-k-sorted-lists

题目内容

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

解题思路

这题目跟我们这周上课讲的一道题目一样，都是将k个有序的链表进行合并，刚好验证具体的思路和其代码实现，首先，合并两个List的函数是我们需要实现的，这里我们先完成合并两个链表的函数，这个十分简单，不过为了内存的节省，我没有使用一般的不停新建node的方式，而是通过不断把list2中应该插入的元素插到node1中，没有使用到新的空间。

而总体的思路跟上课说的一致，都是将两两链表分别合并，再两两合并新的链表，直到剩下一个链表，和归并排序的思路类似。这题目的初始状态相当于是归并排序的运行到中间过程的某个状态。整体思路老师上课的时候讲的也很清楚，这里就不多赘述了。

题目代码

class Solution {
public
    ListNode* mergeTwoLists(ListNode* node1, ListNode* node2) {
        if (node1 == nullptr)
            return node2;
        if (node2 == nullptr)
            return node1;
        ListNode* n1 = nullptr, *n2 = nullptr, *head = nullptr, *preNode = nullptr;
        node1->val < node2->val ? (n1 = node1, n2 = node2) : (n1 = node2, n2 = node1);
        head = n1;
        while (n1 != nullptr && n2 != nullptr) {
            if (n1->val <= n2->val) {
                preNode = n1;
                n1 = n1->next;
            } else {
                auto *nodeTmp = n2->next;
                n2->next = n1;
                preNode->next = n2;
                preNode = n2;
                n2 = nodeTmp;
            }
        }
        if (n1 == nullptr) preNode->next = n2;
        return head;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        for (int i = 0; i < lists.size() - 1; i += 2) {
            auto *p1 = lists[i], *p2 = lists[i + 1];
            lists.emplace_back(mergeTwoLists(p1, p2));
        }
        return lists.back();
    }
};